BFS explores level-by-level using a **queue**. We'll use the `deque` object we imported earlier for an efficient queue implementation.
Guidance for Step 5
- Initialization: Add the `start_node` to both the `queue` and the `visited` set.
- Loop Condition: The `while` loop should continue as long as the `queue` is not empty.
- Process Node: Inside the loop, after dequeuing a node into `u`, print the value of `u`.
- Enqueue Neighbors: For an unvisited neighbor `v`, you must do two things: add `v` to the `visited` set, and then add `v` to the `queue`.
def solve_bfs(start_node, adj, U):
visited = set()
queue = deque()
# 1. Add the start node to the queue and mark as visited
queue.append(______)
visited.add(______)
# 2. Loop while the queue is not empty
while ______:
# 3. Dequeue a node and print it
u = queue.popleft()
print(______, end=' ')
# 4. Enqueue all unvisited neighbors
for v in adj[u]:
if v not in visited:
visited.add(______)
queue.append(______)
Copied!